#define _CRT_SECURE_NO_WARNINGS 1


//#include <stdio.h>
//#include <stdlib.h>
//
//struct ListNode
//{
//	int val;
//	struct ListNode* next;
//};
//
//struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
//{
//	struct ListNode* curA = headA;
//	struct ListNode* curB = headB;
//
//	int lenA = 0;
//
//	while (curA->next)
//	{
//		++lenA;
//		curA = curA->next;
//	}
//	
//	int lenB = 0;
//
//	while (curB->next)
//	{
//		++lenB;
//		curB = curB->next;
//	}
//
//	//不相交
//	if (curA != curB)
//	{
//		return NULL;
//	}
//
//	int gap = abs(lenA - lenB);
//	//因为我们不知道A长还是B长，所以我们要用假设法，先假设A长，如果不对，再调换一下就行
//	struct ListNode* longList = headA;
//	struct ListNode* shortList = headB;
//
//	if (lenB > lenA)
//	{
//		longList = headB;
//		shortList = headA;
//	}
//
//	//让长的先走gap步
//	while (gap--)
//	{
//		longList = longList->next;
//	}
//
//	//再同时走，找交点
//	while (longList != shortList)
//	{
//		longList = longList->next;
//		shortList = shortList->next;
//	}
//
//	return longList;
//}



//#include <stdio.h>
//
//struct ListNode
//{
//	int val;
//	struct ListNoe* next;
//};
//
//struct ListNode* FindKthToTail(struct ListNode* pListHead, int k)
//{
//	struct ListNode* slow = pListHead, * fast = pListHead;
//
//	//fast先走k步
//	while (k--)
//	{
//		//k还没有减到0，链表已经空了，说明k大于链表的长度
//		if (NULL == fast)
//		{
//			return NULL;
//		}
//
//		fast = fast->next;
//	}
//
//	//slow和fast同时走，fast走到空，slow就是倒数第k个
//	while (fast)
//	{
//		slow = slow->next;
//		fast = fast->next;
//	}
//
//	return slow;
//}




//#include <stdbool.h>
//
//struct ListNode
//{
//	int val;
//	struct ListNode* next;
//};
// 
//
//bool hasCycle(struct ListNode* head)
//{
//	struct ListNode* slow = head, * fast = head;
//
//	while (fast && fast->next)
//	{
//		slow = slow->next;
//		fast = fast->next->next;
//
//		if (slow == fast)
//		{
//			return true;
//		}
//	}
//
//	return false;
//}




//#include <stdio.h>
//
//struct ListNode
//{
//	int val;
//	struct ListNode* next;
//};
//
//struct ListNode* detectCycle(struct ListNode* head)
//{
//	struct ListNode* slow = head, * fast = head;
//
//	while (fast && fast->next)
//	{
//		slow = slow->next;
//		fast = fast->next->next;
//
//		if (slow == fast)
//		{
//			struct ListNode* meet = slow;
//
//			while (meet != head)
//			{
//				meet = meet->next;
//				head = head->next;
//			}
//
//			return meet;
//		}
//	}
//
//	return NULL;
//}



#include <stdio.h>
#include <stdlib.h>

struct ListNode
{
	int val;
	struct ListNode* next;
};

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{
	struct ListNode* curA = headA;
	struct ListNode* curB = headB;

	int lenA = 0;

	while (curA->next)
	{
		++lenA;
		curA = curA->next;
	}

	int lenB = 0;

	while (curB->next)
	{
		++lenB;
		curB = curB->next;
	}

	//不相交
	if (curA != curB)
	{
		return NULL;
	}

	int gap = abs(lenA - lenB);
	struct ListNode* longList = headA;
	struct ListNode* shortList = headB;

	if (lenB > lenA)
	{
		longList = headB;
		shortList = headA;
	}

	//让长的先走gap步
	while (gap--)
	{
		longList = longList->next;
	}

	//再同时走，找交点
	while (longList != shortList)
	{
		longList = longList->next;
		shortList = shortList->next;
	}

	return longList;
}

struct ListNode* detectCycle(struct ListNode* head)
{
	struct ListNode* slow = head, * fast = head;

	while (fast && fast->next)
	{
		slow = slow->next;
		fast = fast->next->next;

		if (slow == fast)
		{
			struct ListNode* meet = slow;
			struct ListNode* headx = meet->next;
			meet->next = NULL;

			return getIntersectionNode(head, headx);
		}
	}

	return NULL;
}